package com.itheima.datastructure.binarysearchtree.binarytree;

import com.itheima.datastructure.stack.LinkedListStack;

//非递归后序遍历
public class E03Leetcode145_1 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(new TreeNode(new TreeNode(4), 2, null),
                1, new
                TreeNode(new TreeNode(5), 3, new TreeNode(6))
        );
        LinkedListStack<TreeNode> stack = new LinkedListStack<>(1000);
        TreeNode curr=root;//代表当前节点
        TreeNode pop=null;//最近一次弹出栈的元素
        while(curr!=null || !stack.isEmpty()){
            if(curr!=null){
                colorPrintln("去："+curr.val,31);
                stack.push(curr);//压入栈，为了记住回来的路
                curr=curr.left;
            }else{
                TreeNode peek=stack.peek();//栈顶元素
                if(peek.right==null || peek.right==pop){ //表示如果没有右子树了或者是刚刚弹出的是右子树
                    pop=stack.pop();
                    colorPrintln("回："+pop.val,34);
                }else{
                    curr=peek.right;
                }
            }
        }
    }
    private static void colorPrintln(String origin,int color){
        System.out.printf("\033[%dm%s\033[0m%n",color,origin);
    }
}
